﻿using System;
using System.Collections.Generic;
using System.Text;

/// <summary>
/// 线性表应用示例
/// </summary>
public class SeqListExample
{
    // 顺序表倒置 O(n)
    public static void ReversSeqList(SeqList<int> L)
    {
        int tmp = 0;
        int len = L.GetLength();
        for (int i = 0; i <= len / 2; i++)
        {
            tmp = L[i];
            L[i] = L[len - i];
            L[len - i] = tmp;
        }
    }

    // 有顺序的两个表进行合并成一个大的有序表 O(m+n)
    public static SeqList<int> Merge(SeqList<int> La, SeqList<int> Lb)
    {
        SeqList<int> Lc = new SeqList<int>(La.Maxsize + Lb.Maxsize);
        int i = 0;
        int j = 0;
        int k = 0;
        // 两个表中都有元素，依次遍历比较
        while ((i <= (La.GetLength() - 1)) && (j <= (Lb.GetLength() - 1)))
        {
            if (La[i] < Lb[j])
            {
                Lc.Append(La[i++]);
            }
            else
            {
                Lc.Append(Lb[j++]);
            }
        }
        // a表中还有数据元素
        while ((i <= (La.GetLength() - 1)))
        {
            Lc.Append(La[i++]);
        }
        // 如果b表中还有数据元素
        while ((j <= (La.GetLength() - 1)))
        {
            Lc.Append((Lb[j++]));
        }
        return Lc;
    }

    // 将 a 表去重成为 b表 O(m+n)
    public SeqList<int> Purge(SeqList<int> La)
    {
        SeqList<int> Lb = new SeqList<int>(La.Maxsize);
        // 将 a 表中的第一个元素赋给b表
        Lb.Append(La[0]);
        // 依次处理a表中的元素
        for (int i = 1; i < La.GetLength(); i++)
        {
            int j = 0;
            // 查看b表中有无与a表中相同的数据元素
            for (j = 0; j <= La.GetLength() - 1; j++)
            {
                // 有相同的数据元素
                if (La[i].CompareTo(Lb[j]) == 0)
                {
                    break;
                }
            }
            // 没有相同的数据元素，将a表中的数据元素附加到b表末尾
            if (j > Lb.GetLength() - 1)
            {
                Lb.Append(La[i]);
            }
        }
        return Lb;
    }
}
